package lanqiao;
import java.util.*;
/**
 * Prev_12E 路径【第十二届】【省赛】【B组】
 * 小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。
 * 小蓝的图由 2021 个结点组成，依次编号 1 至 2021。
 * 对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点之间没有边相连；
 * 如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条长度为 a 和 b 的最小公倍数的无向边相连。
 * 例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无向边，长度为 24；
 * 结点 15 和结点 25 之间有一条无向边，长度为 75。
 * 请计算，结点 1 和结点 2021 之间的最短路径长度是多少。
 */
public class Prev_12E {
    private static int min = Integer.MAX_VALUE;
    public static void main(String[] args) {
        dfs(1, 0);
        System.out.println(min);
    }

    public static void dfs(int index, int sum) {
        //边界条件
        if(index == 2021) {
            min = Math.min(min, sum);
            return;
        }

        for(int i = index + 1; i <= index + 21 && i <= 2021; i++){
            int l = route(index, i);
            dfs(i, sum + l);
        }
    }

    public static int route(int a, int b) {
        for(int i = b; ; i += b){
            if(i % a == 0){
                return i;
            }
        }
    }
}
